In recent years, there has been much excitement in the digital communications and coding community about a class of error correcting codes which are very powerful and yet can be decoded practically using iterative algorithms. Two well-known examples are turbo codes and low-density parity-check (LDPC) codes.
See for example Berrou, C., and Glavieux A., and Thitimajshima, P. “Near Shannon limit error-correcting coding: turbo codes,” in Proc. IEEE ICC'93, Geneva, Switzerland, 1993, pp. 1064-1070 and Gallager, R. G., “Low-density parity check codes,” IRE Trans. Inform. Theory, vol. 8, pp. 21-28 January 1962.
The iterative algorithms can be most naturally described using graph representations of the codes. The execution of the algorithms can be described as performing certain computations at the nodes of the graph and passing real messages (soft information) along the edges, in both directions and iteratively. There are only a small number of different types of nodes in terms of their computations. In fact, this number is only two and three for LDPC codes and turbo codes, respectively.
The need for floating point computations and the iterative nature of these decoding algorithms have motivated some very recent research on the analog electronic implementation of the algorithms.
See for example S. Hemati and A. H. Banihashemi, “New Analog VLSI Circuits for Iterative Decoding,” Proceedings of the 21st Biennial Symposium on Communications, Queen's University, Kingston, Ontario, Canada, pp. 261-263, Jun. 2-5, 2002; S. Hemati and A. H. Banihashemi, “Iterative Decoding in Analog CMOS,” Proceedings of the 13th ACM Great Lakes Symposium on VLSI, ACM GLSVLSI 2003, Washington D.C., USA, pp. 15-20, Apr. 27-29, 2003; S. Hemati and A. H. Banihashemi, “Full CMOS Min-Sum Analog Iterative Decoder,” Proceedings of the 2003 IEEE International Symposium on Information Theory, ISIT2003, Yokohama, Japan, pp. 347, Jun. 29-Jul. 4, 2003; S. Hemati and A. H. Banihashemi, “Analog Asynchronous Iterative Decoding, Different Dynamics with Better Performance,” 2nd Analog Decoding Workshop Zürich, Switzerland, September 2003; S. Hemati and A. H. Banihashemi, “A Current-Mode Maximum Winner-Take-All Circuit with Low Voltage Requirement for Min-Sum Analog Iterative Decoders,” Proceedings of the 10th IEEE International Conference on Electronics, Circuits and Systems, ICECS2003, Sharjah, UAE, pp 5-8, Dec. 14-17, 2003; S. Hemati and A. H. Banihashemi, “On the Dynamics of Analog Asynchronous Iterative Decoders,” Proceedings of the 41st Annual Allerton Conference on Communication, Control and Computing, University of Illinois, US, pp. 1679-1687, Oct. 1-3, 2003; Hagenauer, J., Moerz, M., and Offer, E., “Analog turbo networks in VLSI: the next step in turbo decoding and equalization,” in Proc. Int. Symp. on Turbo Codes and Related Topics, Brest, France, September 2000, pp. 209-218, Loeliger, H. A., Lustenberger, F., Helfenstein, M., and Tarkoy, F., “Probability propagation and decoding in analog VLSI,” IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 837-843, February 2001 and Winstead, C., Dai, J., Little, S., Yong-Bin, K., and Jin Kim, W., “Analog MAP decoder for (8, 4) Hamming code in subthreshold CMOS”, in Proc. Advanced Research in VLSI conference, 2001, pp. 132-147.
In analog implementations, each node in the graph acts as a computational module which communicates asynchronously with other nodes of the graph through edges. Iterations are thus eliminated and are replaced by the settling behaviour of the system. This is projected to improve the ratio of speed to power consumption by two orders of magnitude.
There are a wide variety of iterative decoding algorithms, each resulting in a different performance/complexity trade-off. Among these, sum-product (SP), also referred to as belief propagation, performs the best but is considered to be the most complex to implement. In its original form, SP requires basic operations of addition and multiplication of real numbers, and thus the name “sum-product.” While implementing adders is rather straightforward and does not require much power and area in an integrated circuit, implementing a large number of high precision digital multipliers is more challenging. In fact, this is one of the reasons for shifting from digital to analog for implementing iterative decoders. In analog circuits, the Gilbert differential multiplier is a well-known solution for implementing multiplication and is widely used in mixer and PLL circuits.
See for example Gray, P. R., and Meyer, R. G., Analysis and Design of Analog Integrated Circuits, third edition, John Wiley & Sons, 1993. In the Gilbert multiplier, bipolar transistors play a key role. In fact, most of the previously reported analog decoders for iterative schemes have been based on SP algorithm, have used the Gilbert multiplier as the core circuit, and have mostly been implemented by BiCMOS technology. BiCMOS technology has the advantage of using fast bipolar transistors together with low power and small size MOSFETs. However, the BiCMOS technology has a complex fabrication process compared to standard CMOS and this translates into higher cost.
There have also been some attempts to implement the SP algorithm with MOSFETs in weak inversion mode (sub-threshold region) where transistors are partially turned on, and behave like slow bipolar transistors. See for example Winstead, C., Dai, J., Little, S., Yong-Bin, K., and Jin Kim, W., “Analog MAP decoder for (8, 4) Hamming code in subthreshold CMOS,” in Proc. Advanced Research in VLSI conference, 2001, pp. 132-147 and Johns, D. A. and Martin, K., Analog Integrated Circuit Design, first edition, John Wiley & Sons, 1997. Sub-threshold circuits in general have the advantage of consuming a very small amount of power, but often suffer from low speed, mismatch problems and low accuracy.
Another iterative decoding algorithm is referred to as “min-sum” (MS), described in, for example, Forney, Jr, G. D. “On iterative decoding and two-way algorithm”, in Proc. Int. Symp. on Turbo Codes and Related Topics, Brest, France, September 1997, pp. 12-25, which can be regarded as an approximation of SP. Other common names for min-sum algorithm are “max-sum”, “max-product”, “max-log MAP” and “BP-based decoding”. For many codes, the performance of MS is slightly (a few tenths of a dB) worse than that of SP. However, it has lower complexity, and unlike SP, does not require an estimate of noise power. More recently, it has also been shown that MS is more robust against quantization noise than SP. See Zarkeshvari, F., and Banihashemi, A. H. “On implementation of min-sum algorithm for decoding low-density parity-check (LDPC) codes,” in Proc. Globecom 2002, Taipei, Taiwan, Nov. 17-21, 2002.
In fact, MS can be implemented digitally by using only 4 bits compared to 6 bits for a similar implementation of SP. Moreover, there are simple modifications of min-sum that can perform very close to sum-product algorithm. These modifications were presented in Zarkeshvari, F., and Banihashemi, A. H. “On implementation of min-sum algorithm for decoding low-density parity-check (LDPC) codes,” in Proc. Globecom 2002, Taipei, Taiwan, Nov. 17-21, 2002; J. Zhao, “Effects of clipping and quantization on min-sum algorithm and its modifications for decoding low-density parity-check codes,” M. Sc. dissertation, Dept. of Systems and Computer Engineering, Carleton University, Ottawa, Canada, 2003; J. Chen and M. Fossorier, “Near optimum universal belief propagation based decoding of low-density parity-check codes,” IEEE Tran. Comm., vol. 50, pp. 406-414, March 2002; J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier and X.-Y. Hu, “Near optimal reduced complexity decoding algorithms for LDPC codes,” Proc. IEEE ISIT, Lausanne, Switzerland, p. 455, Jun. 30-Jul. 5, 2002; J. Chen and M. Fossorier, “Density evolution for two improved BP-based decoding algorithms of LDPC codes,” IEEE Comm. Lett., vol. 6, no. 5, pp. 208-210, May 2002; J. Chen and M. Fossorier, “Density evolution for BP-based decoding algorithms of LDPC codes and their quantized versions,” Proc. IEEE Globecom, pp. 1378-1382, November 2002. These modifications involve reducing the absolute value of the outgoing messages in parity-check nodes and performing clipping.
Because of imperfections in the fabrication process, the problem of mismatch in large analog integrated circuits becomes very important and the higher robustness in min-sum can also greatly help in mitigating this problem.